import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description: 二叉树基本操作
 * User: LXW
 * Date: 2022-02-25
 * Time: 18:38
 */
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node(int val) {
        this.val = val;
    }
}
public class Test {

    // 遍历思路-求结点个数
    static int size = 0;
    public static void getSize1(Node root) {
        if (root == null) {
            return;
        }
        size++;
        getSize1(root.left);
        getSize1(root.right);
    }
    // 子问题思路-求结点个数
    public static int getSize2(Node root) {
        if (root == null) {
            return 0;
        }
        return (getSize2(root.left) + getSize2(root.right)) + 1;
    }
    // 遍历思路-求叶子结点个数
    static int leafSize = 0;
    public static void getLeafSize1(Node root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            leafSize++;
        }
        getLeafSize1(root.left);
        getLeafSize1(root.right);
    }
    // 子问题思路-求叶子结点个数
    int getLeafSize2(Node root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafSize2(root.left) + getLeafSize2(root.right);
    }
    // 子问题思路-求第 k 层结点个数
    int getKLevelSize(Node root, int k) {
        if (root == null || k <= 0) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
       return getKLevelSize(root.left,k-1) +getKLevelSize(root.right,k-1);
    }
    // 获取二叉树的高度
    int getHeight(Node root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getHeight(root.left),getHeight(root.right)) + 1;
    }
    // 查找 val 所在结点，没有找到返回 null
// 按照 根 -> 左子树 -> 右子树的顺序进行查找
// 一旦找到，立即返回，不需要继续在其他位置查找
    public static Node find(Node root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        Node node = find(root.left,val);
        if (node != null) {
            return node;
        }
        node = find(root.right,val);
        if (node != null) {
            return node;
        }
        return null;
    }
    /**
     * 是不是完全二叉树
     * @param root
     * @return
     */
    boolean isCompleteTree(Node root) {
        Queue<Node> queue =new LinkedList<>();
        if (root == null) {
            return true;
        }
        queue.offer(root);
        while(!queue.isEmpty()) {
            Node cur = queue.poll();
            if (cur != null) {
                queue.offer(root.left);
                queue.offer(root.right);
            }else {
                break;
            }
        }
        while(!queue.isEmpty()) {
            Node top = queue.peek();
            if (top != null) {
                return false;
            }else {
                queue.poll();
            }
        }
        return true;
    }
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2= new Node(2);
        Node node3= new Node(4);
        Node node4= new Node(5);
        Node node5= new Node(6);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        Node cur = find(node1, 2);
        System.out.println(cur);

    }
}
